package madixin.t122;

class Solution {
    //动态规划
    public int maxProfit(int[] prices) {
        int len = prices.length;
        if (len < 2) {
            return 0;
        }

        int[] cash = new int[prices.length];
        int[] stock = new int[prices.length];
        cash[0] = 0;
        stock[0] = -prices[0];

        for (int i = 1; i < prices.length; i++) {
            cash[i] = Math.max(cash[i - 1], stock[i - 1] + prices[i]);
            stock[i] = Math.max(cash[i - 1] - prices[i], stock[i - 1]);
        }

        return cash[prices.length - 1];
    }

    //贪心
    public int maxProfit1(int[] prices) {
        int profit = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i - 1]) {
                profit += prices[i] - prices[i - 1];
            }
        }
        return profit;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.maxProfit(new int[]{7, 1, 5, 3, 6, 4}));
        System.out.println(s.maxProfit(new int[]{1, 2, 3, 4, 5}));
        System.out.println(s.maxProfit(new int[]{7, 6, 4, 3, 1}));
    }
}